package com.xxwy.sort.nlogn;

import com.xxwy.sort.Sort;
import com.xxwy.sort.SortHelper;

import java.util.Iterator;

/**
 * @author xxwy
 */
public class QuickSort3 implements Sort {
    @Override
    public void sort(int[] array, int n) {
        quickSort3(array, 0, n - 1);
    }

    /**
     * arr[l...r]
     * <v =v >=v
     *
     * @param array
     * @param l
     * @param r
     */
    private void quickSort3(int[] array, int l, int r) {
        if (l >= r) {
            return;
        }
        // partition
        int e = array[l];
        int lt = l; //<v]
        int gt = r + 1;//>v
        int i = l+1; // =v
        while (i < gt){
            if(array[i] < e){  // <v+1换
                SortHelper.swap(array,lt+1,i);
                i++;
                lt++;
            }else if(array[i]>e){
                SortHelper.swap(array,gt-1,i);
                gt--;
            }else { //v
                i++;
            }
        }
        SortHelper.swap(array,l,lt);

        //递归
        quickSort3(array,l, lt-1);
        quickSort3(array,gt,r);
    }
}
